package java学习.算法.二叉树;

/**
 * **************
 * 项目名称: 蓝桥杯 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦 <br/>
 * 创建时间: 2022/5/3 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 二叉搜索树的后序遍历 {

    /**
             若它的左子树不为空，则左子树上所有结点的值都小于根结点的值。
             若它的右子树不为空，则右子树上所有结点的值都大于根结点的值。
             它的左右子树也分别是二叉搜索树。

     * @param sequence
     * @return 递归。
     * 输入数组： 后序遍历，判断是否正确：后序的话，左右中 最后的为 中节点。
     */
     /*
     简言之， 左子树的值都比根节点小， 右子树的值都比根节点大

      */
    public boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence.length<=0){
            return false;
        }
        return   VerifySquenceOfBST1(sequence,0,sequence.length-1);
    }

    //
    public boolean VerifySquenceOfBST1(int [] sequence,int start ,int end) {
        if (start>=end){
            // 存在比根节点大，说明现在没有左子树了，都是右子树，肯定是后序.
            return true;
        }
        int root = sequence[end]; // 根节点。
        // 现在去找到  左右子树的区分：

        int i = 0;
        for ( i = 0; i < end; i++) {
            if (sequence[i]>root){
//            找到了  // 在这写 赋值就报错？？？
                break;
            }
        }
        for (int j = i; j <end ; j++) {
            if (sequence[j]<root){
                // 当然现在节点往后 都是>root 若违反，false
                return false;
            }
        }

        // 继续判断 root的左右子树
        boolean a = VerifySquenceOfBST1(sequence, start, i-1);
        boolean b = VerifySquenceOfBST1(sequence, i, end-1);

        // 当然  左右子树都得是二叉搜索树

        return a&&b;

    }
}
